package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * 在二叉搜索树中寻找第k小的数
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/5/5 10:44
 */
public class KthSmallest {

    private int k = 0;
    private int traversed = 0;
    private int res = 0;

    public int search(TreeNode root, int k) {
        this.k = k;
        traverse(root);
        return res;
    }

    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.left);
        traversed++;
        if (traversed == k) {
            res = root.val;
            return;
        } else if (traversed > k) {
            return;
        }
        traverse(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);
        KthSmallest kthSmallest = new KthSmallest();
        kthSmallest.search(root, 4);
        System.out.println(kthSmallest.res);
    }

}
